// https://leetcode.cn/problems/fibonacci-number/

// 题干：斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
//       F(0) = 0，F(1) = 1
//       F(n) = F(n - 1) + F(n - 2)，其中 n > 1
//       给定 n ，请计算 F(n) 。

// 示例：输入：n = 4
//       输出：3

// 碎语：老题目，这次采用记忆化搜索的方法来解决
//       使得递归由指数级别的时间复杂度变为线性级别的时间复杂度
//       添加一个备忘录即可，再递归每次返回的时候将结果放到备忘录里面
//       在每次进入递归的时候，查询一下备忘录有无已经存入的数据

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    int memo[31]; // memory
    int dp[31];
public:
    int fib(int n)
    {
        // 动态规划
        dp[0] = 0, dp[1] = 1;
        for (int i = 2 ; i <= n ; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];

        // 记忆化搜索
        // 初始化
//        memset(memo, -1, sizeof(memo));
//        return dfs(n);
    }

    int dfs(int n)
    {
        // 先往备忘录查询一下(大剪枝)
        if (memo[n] != -1) return memo[n];

        // 返回之前放进备忘录里面
        if (n == 0 || n == 1)
        {
            memo[n] = n;
            return n;
        }
        memo[n] = dfs(n - 1) + dfs(n - 2);

        return memo[n];
    }
};

int main()
{
    Solution sol;
    int n;

    cin >> n;
    cout << sol.fib(n) << endl;
    return 0;
}

// PS:另一种解法动态规划的概念流程解释
//    动态规划与记忆化搜索的本质是一样的：首先，全部是暴力搜索
//    对优化解法的优化：把已经计算过的值存起来，等到需要的时候再存起来

//  1.确定状态表示 dp[i]表示第i个斐波那契数 -> 对应dfs函数的含义
//  2.推导状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]
//  3.初始化 dp[0] = 1,dp[1] = 1 -> 对应递归出口
//  4.确定填表顺序 填写备忘录的顺序(从左往右)
//  5.确定返回值 dp[n] -> 主函数是怎样调用dfs